Sum of nodes of Linked List whose contains values with exactly three factors |
您所在的位置：网站首页 › scala sum › Sum of nodes of Linked List whose contains values with exactly three factors |
|
Given a singly linked list containing N nodes, the task is to find the sum of all possible nodes of the list which contains value with exactly three distinct factors. Examples: Input: 1 -> 2 -> 4 -> 5 Output: 4 Explanation: Factors of 2 are {1, 2} Factors of 3 are {1, 3} Factors of 4 are {1, 2, 4} Factors of 5 are {1, 5} Since only 4 contains three distinct factors. Therefore, the required output is 4. Input: 1 -> 6 -> 8 -> 10 Output: 0 Approach: The idea is based on the fact that if a number is a prime number, then the square of the number contains exactly three distinct factors. Follow the steps below to solve the problem: Initialize a variable, say nodeSum, to store the sum of nodes which contains value with exactly three distinct factors.Traverse the linked list and for each node, check if the square root of the current nodes is a prime number or not. If found to be true, then increment nodeSum by the value of current node.Finally, print the value of nodeSum.Below is the implementation of the above approach: C++// C++ program to implement// the above approach #include using namespace std; // Structure of a// singly Linked Liststruct Node { // Stores data value // of a Node int data; // Stores pointer // to next Node struct Node* next;}; // Function to insert a node at the// beginning of the singly Linked Listvoid push(Node** head_ref, int new_data){ // Create a new Node Node* new_node = new Node; // Insert the data into // the Node new_node->data = new_data; // Insert pointer to // the next Node new_node->next = (*head_ref); // Update head_ref (*head_ref) = new_node;} // Function to check if a number// is a prime number or notbool CheckPrimeNumber(int n){ // Base Case if (n next; } // Return sum return nodeSum;} // Driver Codeint main(){ // Stores head node of // the linked list Node* head = NULL; // Insert all data values // in the linked list push(&head, 5); push(&head, 4); push(&head, 2); push(&head, 1); cout |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |